{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Traffic Light Controlled Intersection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Concurrency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #concurrency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #多线程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: carArrived"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #红绿灯路口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这是两条路的交叉路口。第一条路是 A 路，车辆可沿&nbsp;1 号方向由北向南行驶，也可沿&nbsp;2 号方向由南向北行驶。第二条路是 B 路，车辆可沿&nbsp;3 号方向由西向东行驶，也可沿 4 号方向由东向西行驶。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/11/exp.png\" style=\"height:417px; width:600px\" /></p>\n",
    "\n",
    "<p>每条路在路口前都有一个红绿灯。红绿灯可以亮起红灯或绿灯。</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><strong>绿灯</strong>表示两个方向的车辆都可通过路口。</li>\n",
    "\t<li><strong>红灯</strong>表示两个方向的车辆都不可以通过路口，必须等待绿灯亮起。</li>\n",
    "</ol>\n",
    "\n",
    "<p>两条路上的红绿灯不可以同时为绿灯。这意味着，当 A 路上的绿灯亮起时，B 路上的红灯会亮起；当 B&nbsp;路上的绿灯亮起时，A&nbsp;路上的红灯会亮起.</p>\n",
    "\n",
    "<p>开始时，A 路上的<strong>绿灯</strong>亮起，B 路上的<strong>红灯</strong>亮起。当一条路上的绿灯亮起时，所有车辆都可以从任意两个方向通过路口，直到另一条路上的绿灯亮起。不同路上的车辆不可以同时通过路口。</p>\n",
    "\n",
    "<p>给这个路口设计一个没有死锁的红绿灯控制系统。</p>\n",
    "\n",
    "<p>实现函数&nbsp;<code>void carArrived(carId, roadId, direction, turnGreen, crossCar)</code>&nbsp;:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>carId</code>&nbsp;为到达车辆的编号。</li>\n",
    "\t<li><code>roadId</code>&nbsp;为车辆所在道路的编号。</li>\n",
    "\t<li><code>direction</code>&nbsp;为车辆的行进方向。</li>\n",
    "\t<li><code>turnGreen</code>&nbsp;是一个函数，调用此函数会使当前道路上的绿灯亮起。</li>\n",
    "\t<li><code>crossCar</code>&nbsp;是一个函数，调用此函数会允许车辆通过路口。</li>\n",
    "</ul>\n",
    "\n",
    "<p>当你的答案避免了车辆在路口出现死锁，此答案会被认定为正确的。当路口已经亮起绿灯时仍打开绿灯，此答案会被认定为错误的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> cars = [1,3,5,2,4], directions = [2,1,2,4,3], arrivalTimes = [10,20,30,40,50]\n",
    "<strong>输出:</strong> [\n",
    "&quot;Car 1 Has Passed Road A In Direction 2&quot;,    // A 路上的红绿灯为绿色，1 号车可通过路口。\n",
    "&quot;Car 3 Has Passed Road A In Direction 1&quot;,    // 红绿灯仍为绿色，3 号车通过路口。\n",
    "&quot;Car 5 Has Passed Road A In Direction 2&quot;,    // 红绿灯仍为绿色，5 号车通过路口。\n",
    "&quot;Traffic Light On Road B Is Green&quot;,          // 2 号车在 B 路请求绿灯。\n",
    "&quot;Car 2 Has Passed Road B In Direction 4&quot;,    // B 路上的绿灯现已亮起，2 号车通过路口。\n",
    "&quot;Car 4 Has Passed Road B In Direction 3&quot;     // 红绿灯仍为绿色，4 号车通过路口。\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]\n",
    "<strong>输出:</strong> [\n",
    "&quot;Car 1 Has Passed Road A In Direction 2&quot;,    // A 路上的红绿灯为绿色，1 号车可通过路口。\n",
    "&quot;Traffic Light On Road B Is Green&quot;,          // 2 号车在 B 路请求绿灯。\n",
    "&quot;Car 2 Has Passed Road B In Direction 4&quot;,    // B 路上的绿灯现已亮起，2 号车通过路口。\n",
    "&quot;Car 3 Has Passed Road B In Direction 3&quot;,    // B 路上的绿灯现已亮起，3 号车通过路口。\n",
    "&quot;Traffic Light On Road A Is Green&quot;,          // 5 号车在 A 路请求绿灯。\n",
    "&quot;Car 5 Has Passed Road A In Direction 1&quot;,    // A 路上的绿灯现已亮起，5 号车通过路口。\n",
    "&quot;Traffic Light On Road B Is Green&quot;,          // 4 号车在 B 路请求绿灯。4 号车在路口等灯，直到 5 号车通过路口，B 路的绿灯亮起。\n",
    "&quot;Car 4 Has Passed Road B In Direction 3&quot;     // B 路上的绿灯现已亮起，4 号车通过路口。\n",
    "]\n",
    "<strong>解释:</strong> 这是一个无死锁的方案。注意，在 A 路上的绿灯亮起、5 号车通过前让 4 号车通过，也是一个<strong>正确</strong>且<strong>可</strong><strong>被接受</strong>的方案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= cars.length &lt;= 20</code></li>\n",
    "\t<li><code>cars.length = directions.length</code></li>\n",
    "\t<li><code>cars.length = arrivalTimes.length</code></li>\n",
    "\t<li><code>cars</code>&nbsp;中的所有值都是唯一的。</li>\n",
    "\t<li><code>1 &lt;= directions[i] &lt;= 4</code></li>\n",
    "\t<li><code>arrivalTimes</code> 是非递减的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [traffic-light-controlled-intersection](https://leetcode.cn/problems/traffic-light-controlled-intersection/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [traffic-light-controlled-intersection](https://leetcode.cn/problems/traffic-light-controlled-intersection/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,2,4]\\n[2,1,2,4,3]\\n[10,20,30,40,50]', '[1,2,3,4,5]\\n[2,4,3,3,1]\\n[10,20,30,40,40]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if roadId != self.road:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "        crossCar()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import threading\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1 \n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      \n",
    "        roadId: int,                     \n",
    "        direction: int,                  \n",
    "        turnGreen: 'Callable[[], None]', \n",
    "        crossCar: 'Callable[[], None]'  \n",
    "    ) -> None:\n",
    "        if self.road==roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import threading\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1 \n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if self.road==roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import threading\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car \n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        \n",
    "        if self.road == roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.greenRoad = 1\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if self.greenRoad == roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.greenRoad = roadId\n",
    "            crossCar()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from threading import Lock\n",
    "\n",
    "class TrafficLight:\n",
    "\n",
    "\n",
    "    def __init__(self):\n",
    "        self.A = Lock()\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if roadId == 1:\n",
    "            if self.A.locked():\n",
    "                self.A.release()\n",
    "                turnGreen()\n",
    "            crossCar()\n",
    "        else:\n",
    "            if not self.A.locked():\n",
    "                self.A.acquire()\n",
    "                turnGreen()\n",
    "            crossCar()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.roadId = 1\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if roadId == self.roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.roadId = roadId\n",
    "            crossCar()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import threading\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1 \n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if self.road==roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if roadId == self.road:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1 \n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "\n",
    "        if self.road==roadId:\n",
    "                crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import threading\n",
    "\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.road = 1 \n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if self.road==roadId:\n",
    "            crossCar()\n",
    "        else:\n",
    "            turnGreen()\n",
    "            self.road = roadId\n",
    "            crossCar()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from threading import Semaphore\n",
    "class TrafficLight:\n",
    "    def __init__(self):\n",
    "        self.light_mtx = Semaphore(1)\n",
    "        self.road1_num_mtx = Semaphore(1)\n",
    "        self.road2_num_mtx = Semaphore(1)\n",
    "        self.light = 1\n",
    "        self.road1_num = 0\n",
    "        self.road2_num = 0\n",
    "\n",
    "    def carArrived(\n",
    "        self,\n",
    "        carId: int,                      # ID of the car\n",
    "        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)\n",
    "        direction: int,                  # Direction of the car\n",
    "        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road\n",
    "        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection\n",
    "    ) -> None:\n",
    "        if roadId == 1:\n",
    "            # update num\n",
    "            self.road1_num_mtx.acquire()\n",
    "            if self.light != roadId:\n",
    "                self.light_mtx.acquire()\n",
    "                self.light = roadId\n",
    "                turnGreen()\n",
    "                self.light_mtx.release()\n",
    "            self.road1_num += 1\n",
    "            self.road1_num_mtx.release()\n",
    "            # other road1 cars can use 'road1_num_mtx' to cross without light block\n",
    "            crossCar()\n",
    "            # after cross, minus the road1_num\n",
    "            self.road1_num_mtx.acquire()\n",
    "            self.road1_num -= 1\n",
    "            if self.road1_num == 0:\n",
    "                # not release the block until all road1 cars cross\n",
    "                self.light_mtx.release()\n",
    "            self.road1_num_mtx.release()\n",
    "        else:\n",
    "            self.road2_num_mtx.acquire()\n",
    "            if self.light != roadId:\n",
    "                self.light_mtx.acquire()\n",
    "                self.light = roadId\n",
    "                turnGreen()\n",
    "                self.light_mtx.release()\n",
    "            self.road2_num += 1\n",
    "            self.road2_num_mtx.release()\n",
    "            crossCar()\n",
    "            self.road2_num_mtx.acquire()\n",
    "            self.road2_num -= 1\n",
    "            if self.road2_num == 0:\n",
    "                self.light_mtx.release()\n",
    "            self.road2_num_mtx.release()"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
